package leetcode_5000;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class _最长重复子串 {
	
	public static void main(String[] args) {
		_最长重复子串 test = new _最长重复子串();
		System.out.println(test.longestRepeatingSubstring("aaaaa"));
		System.out.println(test.longestRepeatingSubstring("aabcaabdaab"));
	}
	
	public int longestRepeatingSubstring(String S) {
        int res = 0;
        char[] s = S.toCharArray();
        int[][]dp = new int[s.length+1][s.length+1];
        Map<Character,List<Integer>> map = new HashMap<>();
        for(int i=0;i<s.length;++i) {
        	List<Integer> index = map.get(s[i]);
        	if(index == null) {
        		index = new ArrayList<Integer>();
        		index.add(i);
        		map.put(s[i], index);
        	}else {
        		for(int j:index) {
        			res = Math.max(res, dp[j][i]+1);
        			dp[j+1][i+1] = dp[j][i]+1;
        		}
        		index.add(i);
        	}
        }
        return res;
    }
}
